package 纯数组;

import java.util.Map;
import java.util.TreeMap;

public class JZ51数组中的逆序对 {

    /**
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，
     * 则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     *
     * 示例 1:
     * 输入: [7,5,6,4]
     * 输出: 5
     *  
     * 限制：
     * 0 <= 数组长度 <= 50000
     */

    public int reversePairs(int[] nums) {
        MergeSort mergeSort=new MergeSort();
        /**
         * 这个想法牛呀!
         */
        return mergeSort.mergeSort(nums);
    }


    static class MergeSort{

        private int mergeSort(int[] arr) {
            int[] tempArr=new int[arr.length];
            return dfs(arr,tempArr,0,arr.length-1);
        }

        private int dfs(int[] arr,int[] tempArr,int left,int right) {

            if(left>=right){
                return 0;
            }

            //先划分
            int mid=(right-left)/2+left;
            int n1=dfs(arr,tempArr,left,mid);//注意不能都-1/+1
            int n2=dfs(arr,tempArr,mid+1,right);
            //后合并
            int n3=m1(arr,tempArr,left,right);
            /**
             * 每小块,左右两边的逆序对个数~
             */
            return n1+n2+n3;
        }

        private int m1(int[] arr,int[] tempArr,int left,int right){

            int mid=(right-left)/2+left;
            int tempStart=left;
            int lStart=left;
            int rStart=mid+1;//契合上层函数右边起点是mid+1

            //如果正好有序
            if(arr[mid]<=arr[rStart]){
                return 0;
            }

            int count=0;

            while (lStart<=mid&&rStart<=right){
                if(arr[lStart]<=arr[rStart]){// '<=' 为稳定排序
                    //左放入
                    tempArr[tempStart]=arr[lStart];
                    lStart++;
                }else{
                    //右放入
                    tempArr[tempStart]=arr[rStart];
                    rStart++;
                    /**
                     * 右边放入,此时说明左边数组的元素都比右边放入的这个大,所以count就加上这么多
                     */
                    count+=(mid-lStart)+1;
                }
                tempStart++;
            }

            //左边没放完
            while (lStart<=mid){
                tempArr[tempStart]=arr[lStart];
                tempStart++;
                lStart++;
            }

            //右边没放完
            while (rStart<=right){
                tempArr[tempStart]=arr[rStart];
                tempStart++;
                rStart++;
            }

            //放回原数组
            for (int i = left; i <= right; i++) {
                arr[i]=tempArr[i];
            }

            return count;
        }

    }

}
